/**
 * @author dengjiangming
 * @date 2025/7/30
 * @description 21. 合并两个有序链表
 */
public class MergeTwoLists {

    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1,MySingleList.ListNode list2) {
        //先创建一个新的链表的头,用于指向链表于方法最后返回
        //创建一个尾指针指向链表的尾部，用于拼接新的结点
        MySingleList.ListNode newLast = null;
        MySingleList.ListNode newHead = null;

        //遍历两个有序链表
        MySingleList.ListNode head1 = list1;
        MySingleList.ListNode head2 = list2;

        while(head1 != null && head2 != null) {
            //合并有序链表
            if(head1.val < head2.val) {
                MySingleList.ListNode curN = head1.next;
                //将head1所指向的结点拼接到newHead后面
                if(newLast == null && newHead == null) {
                    newLast = head1;
                    newHead = head1;
                }else {
                    newLast.next = head1;
                    newLast = head1;
                }

                head1 = curN;

            }else{
                MySingleList.ListNode curN = head2.next;
                if(newLast == null && newHead == null) {
                    newLast = head2;
                    newHead = head2;
                }else {
                    newLast.next = head2;
                    newLast = head2;
                }

                head2 = curN;
            }
        }

        //合并余下的数据
        while(head1 != null) {
            MySingleList.ListNode curN = head1.next;
            if(newLast == null && newHead == null) {
                newLast = head1;
                newHead = head1;
            }else {
                newLast.next = head1;
                newLast = head1;
            }

            head1 = curN;
        }

        while(head2 != null) {
            MySingleList.ListNode curN = head2.next;

            if(newLast == null && newHead == null) {
                newLast = head2;
                newHead = head2;
            }else {
                newLast.next = head2;
                newLast = head2;
            }

            head2 = head2.next;
        }
        return newHead;
    }

    public static void main(String[] args) {
        MySingleList list1 = new MySingleList();


        MySingleList list2 = new MySingleList();
        list2.addLast(0);

        MySingleList.ListNode mergeTwoLists = mergeTwoLists(list1.head,list2.head);
        MySingleList mergeList = new MySingleList();
        mergeList.head = mergeTwoLists;
        mergeList.disPlay(mergeList.head);
    }
}
